/*
 * Created on April 30, 2005
 *
 * Copyright (c) Patrick Armstrong 2002-2007. All Rights Reserved
 */
package org.dime.mine.bot;

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import org.dime.mine.bot.AwareBoard.AwareLocation;
import org.dime.mine.bot.ZonedBoard.Zone;
import org.dime.mine.game.Board;
import org.dime.mine.game.actions.Mark;

/**
 * Burnout // TODO Add type summary
 * 
 * @author Owner
 */
public class Burnout extends AbstractStrategy
{
    private static final int INFINITY = Integer.MAX_VALUE;

    @Override
    public boolean execute(Board board)
    {
        ZonedBoard zBoard = new ZonedBoard(board);
        boolean hasCycle = false;
        for (Zone z : zBoard.getZones())
        {
            hasCycle |= z.isCyclic();
        }
        if (hasCycle)
            System.out.println(zBoard);
        return false;
    }

    public boolean execute2(Board board)
    {
        AwareBoard awareBoard = new AwareBoard(board);
        AwareBoard[] zones = null;

        int marksNeeded = awareBoard.getMines() - awareBoard.getMarks();
        int marksUsed = 0;
        Set<Board.Location> s = new HashSet<Board.Location>();
        List<Board.Location> l = new LinkedList<Board.Location>();
        for (int i = 0; i < zones.length; i++)
        {
            marksUsed += helper(new TestBoard(zones[i]), 0, marksNeeded + 1, l,
                    s);
        }

        boolean flag = false;
        if (marksUsed == marksNeeded)
        {
            for (int i = 0; i < awareBoard.getRows(); i++)
            {
                for (int j = 0; j < awareBoard.getColumns(); j++)
                {
                    if (awareBoard.check(i, j) == Board.NOT_OPEN)
                    {
                        if (!s.contains(awareBoard.getLocation(i, j)))
                        {
                            board.open(i, j);
                            flag = true;
                        }
                    }
                }
            }
        }

        return flag;
    }

    // TODO handle interrupts
    private int helper(TestBoard zone, int depth, int maxDepth,
            List<Board.Location> l, Set<Board.Location> s)
    {
        // prune this branch if the depth already exceeds the maximum
        // depth or if it is not valid
        if (depth > maxDepth || !zone.isValid())
            return INFINITY;

        Iterator<? extends AwareLocation> it = zone.getUnsolvedLocations()
                .iterator();
        if (!it.hasNext())
        {
            s.addAll(l);
            return depth;
        }

        AwareBoard.AwareLocation pos = it.next();
        int bestDepth = INFINITY;
        Iterator<AwareLocation> posIt = zone.getNeighborhood(pos.getRow(),
                pos.getColumn()).iterator();
        AwareBoard.AwareLocation border;
        Mark mark;
        while (posIt.hasNext())
        {
            border = posIt.next();
            if (border.isUnknown())
            {
                mark = new Mark(border);
                mark.execute();
                l.add(border);

                bestDepth = helper(zone, depth + 1, maxDepth, l, s);

                if (bestDepth <= maxDepth)
                    maxDepth = bestDepth;

                l.remove(l.size() - 1);
                mark.undo();
            }
        }

        return Math.min(bestDepth, maxDepth);
    }
}